// 动态规划解法
function climbStairs3(n) {
    const dp = []
    dp[0] = 1
    dp[1] = 1
    for(let i=2;i<=n;i++){
        dp[i] = dp[i-1]+dp[i-2]
    }
    return dp[n];
}

// 递归方式解法
function climbStairs1(n) {
    const mapObj = new Map();
    const whiteListNum = [1, 2]
    if (whiteListNum.includes(n)) {
        return n;
    }
    if(mapObj.get(n) != null) {
        return mapObj.get(n);
    } else {
        mapObj.set(n, climbStairs(n - 1) + climbStairs(n - 2))
        return mapObj.get(n)
    }
}

// 循环方式解法
function climbStairs2(n) {
    const mapObj = new Map();
    const whiteListNum = [1, 2]
    if (whiteListNum.includes(n)) {
        return n;
    }
    let pre = 2;
    let prePre = 1;
    let result = 0;
    for(let i=3;i<=n;++i){
        result = pre + prePre
        prePre = pre;
        pre = result
    }
    return result
}